package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 *      216. 组合总和 III
 *      
 *      找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 *      说明：
 *      所有数字都是正整数。
 *      解集不能包含重复的组合。
 *      示例 1:
 *
 *      输入: k = 3, n = 7
 *      输出: [[1,2,4]]
 *
 *   解题过程：
 *      一开始递归使用的是 dfs(k, n, result, path, temp, begin + 1, used)，由于 begin + 1 故此出现了重复的数据。正确的是 i + 1
 *      输入：
 *          3
 *          9
 *      输出：
 *          [[1,2,6],[1,3,5],[1,5,3],[2,3,4],[2,4,3],[3,2,4],[4,2,3]]   =>   出现重复数据
 *      预期结果：
 *          [[1,2,6],[1,3,5],[2,3,4]]
 *
 *      后续发现，其实没必要使用 used[]，因为循环是从 i = begin 开始的，这样子就可以排除使用过的数据了
 *      其实 curSum 也可以省去，只要 target = 0，说明就是答案
 */
public class _216_combinationSum3 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(k, n, result, path, 0, 1);
        return result;
    }

    private void dfs(int k, int n, List<List<Integer>> result, List<Integer> path, int curSum, int begin) {
        if (path.size() == k && curSum == n) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = begin; i < 9; i++) {
            path.add(i);
            curSum = curSum + i;
            dfs(k, n, result, path, curSum, i + 1);
            path.remove(path.size() - 1);
            curSum = curSum - i;
        }
    }
}
